class BstNode {
  constructor(key, value) {
    this.left = null
    this.key = key
    this.value = value
    this.right = null
  }
}
class Bst {
  constructor() {
    this.root = null
  }
  insert(key, value) {
    const newNode = new BstNode(key, value)
    if (this.root === null) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
  }
  insertNode(tree, node) {
    if (node.key < tree.key) {
      if (tree.left === null) {
        tree.left = node
      } else {
        this.insertNode(tree.left, node)
      }
    } else {
      if (tree.right === null) {
        tree.right = node
      } else {
        this.insertNode(tree.right, node)
      }
    }
  }
  // 先序遍历
  preOrderTral(hander, order) {
    this.preOrderTralNode(this.root, hander, order)
  }
  preOrderTralNode(node, hander, order) {
    if (node) {
      // 处理经过的节点
      switch (order) {
        case '先序遍历':
          hander(node)
          this.preOrderTralNode(node.left, hander, order)
          this.preOrderTralNode(node.right, hander, order)
          break
        case '中序遍历':
          this.preOrderTralNode(node.left, hander, order)
          hander(node)
          this.preOrderTralNode(node.right, hander, order)
          break
        case '后序遍历':
          this.preOrderTralNode(node.left, hander, order)
          this.preOrderTralNode(node.right, hander, order)
          hander(node)
          break
      }
    }
  }
  min() {
    let node = null
    let thatNode = this.root
    while (thatNode != null) {
      node = thatNode
      thatNode = thatNode.left
    }
    return node.key
  }
  max() {
    let node = null
    let thatNode = this.root
    while (thatNode != null) {
      node = thatNode
      thatNode = thatNode.right
    }
    return node.key
  }
  search(key) {
    let thatNode = this.root
    if (thatNode) {
      while (thatNode != null) {
        if (key < thatNode.key) {
          thatNode = thatNode.left
        } else if (key > thatNode.key) {
          thatNode = thatNode.right
        } else {
          return thatNode
        }
      }
    }
    return false
  }
  searchParent(key) {
    let pNode = null
    let thatNode = this.root
    if (thatNode) {
      while (thatNode != null) {
        if (key < thatNode.key) {
          pNode = thatNode
          thatNode = thatNode.left
        } else if (key > thatNode.key) {
          pNode = thatNode
          thatNode = thatNode.right
        } else {
          return pNode
        }
      }
    }
    return false
  }
  remove(key) {
    //   1.找到删除的节点,没有就返回
    if (!this.search(key)) return null
    //   找到节点
    const currentNode = this.search(key)
    const pNode = this.searchParent(key)
    //   1.叶子节点
    if (currentNode.left === null && currentNode.right === null) {
      if (pNode.left === currentNode) {
        pNode.left = null
      } else {
        pNode.right = null
      }
      return currentNode
    }
    if (currentNode.left !== null && currentNode.right === null) {
      console.log('左子节点')
      if (pNode.left === currentNode) {
        pNode.left = currentNode.left
      } else {
        pNode.right = currentNode.left
      }
      return currentNode
    }
    if (currentNode.left === null && currentNode.right !== null) {
      console.log('右子节点')
      if (pNode.left === currentNode) {
        pNode.left = currentNode.right
      } else {
        pNode.right = currentNode.right
      }
      return currentNode
    }
    if (currentNode.left !== null && currentNode.right !== null) {
      console.log('双子节点')
      const successor = this.getSuccessor(currentNode)
      // 如果是根
      // 没写完
      return
    }
  }
  // 查找后继
  getSuccessor(node) {
    let Successor = node
    let thatNode = node.right
    while (thatNode != null) {
      Successor = thatNode
      thatNode = thatNode.left
    }
    return Successor
  }
  // 查找前驱
  getPrecursor(node) {
    let Precursor = node
    let thatNode = node.left
    while (thatNode != null) {
      Precursor = thatNode
      thatNode = thatNode.right
    }
    return Precursor
  }
}
const bst = new Bst()
bst.insert(2, 'aaa')
bst.insert(1, 'ccc')
bst.insert(6, 'bbb')
// bst.insert(9, 'ddd')
bst.insert(3, 'eee')

// let arr = []
// bst.preOrderTral(node => arr.push(node.key), '先序遍历')
// console.log(arr)
// arr = []
// bst.preOrderTral(node => arr.push(node.key), '中序遍历')
// console.log(arr)
// arr = []
// bst.preOrderTral(node => arr.push(node.key), '后序遍历')
// console.log(arr)
// arr = []
// console.log(bst.min())
// console.log(bst.max())
// console.log(bst.search(3))
console.log(bst.remove(3))
console.log(bst.search(6))
